#include "pc.hpp"

template<std::int64_t POW_OF_2_>
std::int64_t roundUp(std::int64_t n)
{
    return (n + POW_OF_2_ - 1) & ~(POW_OF_2_ - 1);
}

template<std::int64_t POW_OF_2_>
std::int64_t roundDown(std::int64_t n)
{
    auto m = roundUp<POW_OF_2_>(n);
    return m > n ? m - POW_OF_2_ : n;
}

inline void print(std::vector<std::size_t> const& v)
{
    std::cout << "[";
    for (auto i = 0uz; i < v.size(); ++i)
    {
        std::cout << v[i];
        if (i + 1 < v.size())
        {
            std::cout << ", ";
        }
    }
    std::cout << "]" << std::endl;
}

namespace rts
{
constexpr auto CE_MTU          = 1212;
constexpr auto CE_MAX_MSG_SIZE = 64 * 1024;

#pragma pack(push)
#pragma pack(1)

/*
+------------------------------------+
|PacketHeader|src_uid|dst_uid|Payload|
+------------------------------------+
*/
struct FixedHeader final
{
    std::uint64_t msg_id; // A random number generated by the sender.
    std::uint16_t msg_len;
    std::uint16_t payload_offset;
    std::uint16_t payload_len;
    std::uint8_t  src_uid_len : 6;
    std::uint8_t  fec_enabled : 1;
    std::uint8_t  require_ack : 1;
    std::uint8_t  dst_uid_len : 6;
    std::uint8_t  reserved    : 2;
};
#pragma pack(pop)

inline FixedHeader* getHeaderPtr(void* p)
{
    return reinterpret_cast<FixedHeader*>(p);
}

inline FixedHeader const* getHeaderPtr(void const* p)
{
    return getHeaderPtr(const_cast<void*>(p));
}

inline std::size_t getFullHeaderSize(void const* p)
{
    auto const hdr = getHeaderPtr(p);
    return sizeof(FixedHeader) + hdr->src_uid_len + hdr->dst_uid_len;
}

inline void copyHeader(void* dst, void const* src, std::size_t const idx)
{
    std::memcpy(dst, src, getFullHeaderSize(src));
    getHeaderPtr(dst)->payload_offset =
        getHeaderPtr(dst)->payload_len * static_cast<std::uint16_t>(idx);
}

inline char* getPayloadPtr(void* p)
{
    auto const hdr      = getHeaderPtr(p);
    auto const uids_len = std::size_t(hdr->src_uid_len + hdr->dst_uid_len);
    return reinterpret_cast<char*>(p) + sizeof(FixedHeader) + uids_len;
}

inline char const* getPayloadPtr(void const* p)
{
    return getPayloadPtr(const_cast<void*>(p));
}

inline void xor64(void const* const p_a,
                  void const* const p_b,
                  std::size_t const size,
                  void*             output)
{
    assert(0 == size % 8);

    auto const  elem_cnt = size / 8;
    auto const* p_u64_a  = reinterpret_cast<std::uint64_t const*>(p_a);
    auto const* p_u64_b  = reinterpret_cast<std::uint64_t const*>(p_b);
    auto*       p_u64_c  = reinterpret_cast<std::uint64_t*>(output);

    for (auto i = std::size_t{}; i < elem_cnt; ++i)
    {
        p_u64_c[i] = p_u64_a[i] ^ p_u64_b[i];
    }
}

struct UserIds final
{
    std::string src_uid;
    std::string dst_uid;
};

inline UserIds getUserIds(FixedHeader const* const hdr)
{
    if (hdr->src_uid_len < 1 || hdr->src_uid_len > 32 || hdr->dst_uid_len < 1 ||
        hdr->dst_uid_len > 32)
    {
        return {};
    }

    auto ret = UserIds{};

    ret.src_uid.resize(2 * (hdr->src_uid_len + 1));
    ret.dst_uid.resize(2 * (hdr->dst_uid_len + 1));
    auto p = reinterpret_cast<char const*>(hdr + 1);

    std::memcpy(ret.src_uid.data(), p, ret.src_uid.size());
    p += ret.src_uid.size();
    std::memcpy(ret.dst_uid.data(), p, ret.dst_uid.size());

    return ret;
}

inline std::vector<std::string> genIndexVectors(std::size_t n)
{
    auto const m = n - 1;

    auto ret = std::vector<std::string>{};
    ret.reserve(n);

    for (auto i = std::size_t{}; i < n; ++i)
    {
        ret.emplace_back();
        ret.back().reserve(m);

        for (auto j = std::size_t{}; j < n; ++j)
        {
            if (j != m - i)
            {
                ret.back().push_back(static_cast<char>(j));
            }
        }
    }

    return ret;
}

inline std::pair<std::string, std::string>
splitIntoIotaStrings(std::string const& str)
{
    auto ret = std::pair<std::string, std::string>{};
    for (auto c : str)
    {
        if (ret.first.empty() || c == ret.first.back() + 1)
        {
            ret.first.push_back(c);
            continue;
        }

        ret.second.push_back(c);
    }

    return ret;
}

inline std::deque<std::vector<char>> fecEncode(char const* const src_uid,
                                               std::size_t const src_uid_len,
                                               char const* const dst_uid,
                                               std::size_t       dst_uid_len,
                                               bool              require_ack,
                                               void const* const msg,
                                               std::size_t const msg_size)
{
    auto       ret           = std::deque<std::vector<char>>{};
    auto const full_hdr_size = src_uid_len + dst_uid_len + sizeof(FixedHeader);
    auto const max_payload_size = CE_MTU - full_hdr_size;

    if (src_uid_len < 1 || dst_uid_len < 1 || src_uid_len > 32 ||
        dst_uid_len > 32 || msg_size > CE_MAX_MSG_SIZE)
    {
        return {};
    }

    auto const msg_id = rand<std::uint64_t>();

    if (max_payload_size >= msg_size)
    {
        ret.emplace_back();
        ret.back().resize(full_hdr_size + msg_size);

        auto hdr            = getHeaderPtr(ret.back().data());
        hdr->msg_id         = msg_id;
        hdr->msg_len        = static_cast<std::uint16_t>(msg_size);
        hdr->payload_offset = 0;
        hdr->payload_len    = static_cast<std::uint16_t>(msg_size);
        hdr->fec_enabled    = false;
        hdr->require_ack    = require_ack;
        hdr->src_uid_len    = static_cast<std::uint8_t>(src_uid_len);
        hdr->dst_uid_len    = static_cast<std::uint8_t>(dst_uid_len);

        auto p = reinterpret_cast<char*>(hdr + 1);
        std::memcpy(p, src_uid, src_uid_len);
        p += src_uid_len;
        std::memcpy(p, dst_uid, dst_uid_len);
        p += dst_uid_len;
        std::memcpy(p, msg, msg_size);

        return ret;
    }

    auto const rounded_max_payload_size = static_cast<std::size_t>(
        roundDown<8>(static_cast<std::int64_t>(max_payload_size)));
    assert(rounded_max_payload_size <= max_payload_size);
    assert(0 == rounded_max_payload_size % 8);

    auto const block_cnt = msg_size % rounded_max_payload_size
                             ? msg_size / rounded_max_payload_size + 1
                             : msg_size / rounded_max_payload_size;

    auto const candidate_payload_size = static_cast<std::size_t>(
        roundUp<8>(static_cast<std::int64_t>(msg_size / block_cnt)));

    auto const payload_size = candidate_payload_size * block_cnt < msg_size
                                ? candidate_payload_size + 8
                                : candidate_payload_size;

    assert(payload_size * block_cnt >= msg_size);
    assert(payload_size * block_cnt < msg_size + payload_size);
    assert(0 == payload_size % 8);

    auto const p_msg = static_cast<char const*>(msg);
    for (auto i = std::size_t{}; i < block_cnt; ++i)
    {
        ret.emplace_back();
        ret.back().resize(full_hdr_size + payload_size);

        auto hdr = getHeaderPtr(ret.back().data());

        if (i > 0)
        {
            std::memcpy(ret.back().data(), ret.front().data(), full_hdr_size);
            hdr->payload_offset = static_cast<std::uint16_t>(i * payload_size);

            assert(i * payload_size <= msg_size);

            if (i * payload_size + payload_size > msg_size)
            {
                std::memcpy(ret.back().data() + full_hdr_size,
                            &p_msg[i * payload_size],
                            msg_size % payload_size);
            }
            else
            {
                std::memcpy(ret.back().data() + full_hdr_size,
                            &p_msg[i * payload_size],
                            payload_size);
            }
        }
        else
        {
            hdr->msg_id         = msg_id;
            hdr->msg_len        = static_cast<std::uint16_t>(msg_size);
            hdr->payload_offset = static_cast<std::uint16_t>(i * payload_size);
            hdr->payload_len    = static_cast<std::uint16_t>(payload_size);
            hdr->fec_enabled    = true;
            hdr->require_ack    = require_ack;
            hdr->src_uid_len    = static_cast<std::uint8_t>(src_uid_len);
            hdr->dst_uid_len    = static_cast<std::uint8_t>(dst_uid_len);

            auto p = reinterpret_cast<char*>(hdr + 1);
            std::memcpy(p, src_uid, src_uid_len);
            p += src_uid_len;
            std::memcpy(p, dst_uid, dst_uid_len);
            p += dst_uid_len;

            assert(msg_size > payload_size);
            std::memcpy(p, p_msg, payload_size);
        }
    }

    auto const fec_start_offset = block_cnt * payload_size;
    auto       idx_vs           = genIndexVectors(block_cnt);
    auto       cache = std::unordered_map<std::string, std::vector<char>>{};
    auto       i     = std::size_t{};

    if (2 == block_cnt)
    {
        ret.emplace_back();
        ret.back().resize(full_hdr_size + payload_size);
        std::memcpy(ret.back().data(), ret.front().data(), full_hdr_size);
        auto hdr            = getHeaderPtr(ret.back().data());
        hdr->payload_offset = static_cast<std::uint16_t>(fec_start_offset);
        std::memcpy(getPayloadPtr(ret.back().data()),
                    getPayloadPtr(ret[0].data()),
                    payload_size);

        ret.emplace_back();
        ret.back().resize(full_hdr_size + payload_size);
        std::memcpy(ret.back().data(), ret.front().data(), full_hdr_size);
        hdr = getHeaderPtr(ret.back().data());
        hdr->payload_offset =
            static_cast<std::uint16_t>(fec_start_offset + payload_size);
        std::memcpy(getPayloadPtr(ret.back().data()),
                    getPayloadPtr(ret[1].data()),
                    payload_size);

        ret.emplace_back();
        ret.back().resize(full_hdr_size + payload_size);
        std::memcpy(ret.back().data(), ret.front().data(), full_hdr_size);
        hdr = getHeaderPtr(ret.back().data());
        hdr->payload_offset =
            static_cast<std::uint16_t>(fec_start_offset + (2 * payload_size));
        xor64(getPayloadPtr(ret[0].data()),
              getPayloadPtr(ret[1].data()),
              payload_size,
              getPayloadPtr(ret.back().data()));

        assert(ret.size() == 5);
        return ret;
    }

    for (auto const& idx_v : idx_vs)
    {
        ret.emplace_back();
        ret.back().resize(full_hdr_size + payload_size);
        std::memcpy(ret.back().data(), ret.front().data(), full_hdr_size);
        auto hdr = getHeaderPtr(ret.back().data());
        hdr->payload_offset =
            static_cast<std::uint16_t>(fec_start_offset + (payload_size * i));

        auto ivp = splitIntoIotaStrings(idx_v);

        auto const fn_build_cache = [&](std::string const& idx_v)
        {
            auto n = idx_v.size();
            if (n < 2)
            {
                return;
            }

            auto key = std::string{};
            key.reserve(n);
            key.push_back(idx_v[0]);
            key.push_back(idx_v[1]);

            auto& value = cache[key];
            value.resize(payload_size);

            xor64(
                ret[static_cast<std::size_t>(idx_v[0])].data() + full_hdr_size,
                ret[static_cast<std::size_t>(idx_v[1])].data() + full_hdr_size,
                payload_size,
                value.data());
            auto p_last_cached_block = value.data();

            for (auto j = std::size_t(2); j < n; ++j)
            {
                key.push_back(idx_v[j]);
                auto pos = cache.find(key);
                if (pos != cache.end())
                {
                    p_last_cached_block = pos->second.data();
                    continue;
                }

                auto tmp = std::vector<char>{};
                tmp.resize(payload_size);

                xor64(ret[static_cast<std::size_t>(idx_v[j])].data() +
                          full_hdr_size,
                      p_last_cached_block,
                      payload_size,
                      tmp.data());
                cache[key]          = std::move(tmp);
                p_last_cached_block = cache[key].data();
            }
        };

        if (ivp.first.size() > 1 && ivp.second.size() > 1) // [2, 2]
        {
            fn_build_cache(ivp.first);
            fn_build_cache(ivp.second);

            xor64(cache[ivp.first].data(),
                  cache[ivp.second].data(),
                  payload_size,
                  getPayloadPtr(ret.back().data()));
        }
        else if (ivp.first.size() > 1 && ivp.second.size() == 1) // [2, 1]
        {
            fn_build_cache(ivp.first);
            auto const blk_idx = static_cast<std::size_t>(ivp.second.front());
            xor64(cache[ivp.first].data(),
                  getPayloadPtr(ret[blk_idx].data()),
                  payload_size,
                  getPayloadPtr(ret.back().data()));
        }
        else if (ivp.first.size() > 1 && ivp.second.empty()) // [2, 0]
        {
            fn_build_cache(ivp.first);
            std::memcpy(getPayloadPtr(ret.back().data()),
                        cache[ivp.first].data(),
                        payload_size);
        }
        else if (ivp.first.size() == 1 && ivp.second.size() > 1) // [1, 2]
        {
            fn_build_cache(ivp.second);
            auto const blk_idx = static_cast<std::size_t>(ivp.first.front());
            xor64(cache[ivp.second].data(),
                  getPayloadPtr(ret[blk_idx].data()),
                  payload_size,
                  getPayloadPtr(ret.back().data()));
        }
        else if (ivp.first.size() == 1 && ivp.second.size() == 1) // [1, 1]
        {
            auto const blk_idx1 = static_cast<std::size_t>(ivp.first.front());
            auto const blk_idx2 = static_cast<std::size_t>(ivp.second.front());
            xor64(getPayloadPtr(ret[blk_idx1].data()),
                  getPayloadPtr(ret[blk_idx2].data()),
                  payload_size,
                  getPayloadPtr(ret.back().data()));
        }
        else if (ivp.first.empty() && ivp.second.size() > 1) // [0, 2]
        {
            fn_build_cache(ivp.second);
            std::memcpy(getPayloadPtr(ret.back().data()),
                        cache[ivp.second].data(),
                        payload_size);
        }
        else // [1, 0], [0, 1], [0, 0]
        {
            std::abort();
        }

        ++i;
    }

    {
        ret.emplace_back();
        ret.back().resize(full_hdr_size + payload_size);
        std::memcpy(ret.back().data(), ret.front().data(), full_hdr_size);
        auto hdr            = getHeaderPtr(ret.back().data());
        hdr->payload_offset = static_cast<std::uint16_t>(fec_start_offset * 2);
        xor64(cache[idx_vs.back()].data(),
              p_msg,
              payload_size,
              ret.back().data() + full_hdr_size);
    }

    return ret;
}

constexpr auto CE_INVALID_INDEX = std::size_t(99999);

struct Atom final
{
    std::size_t idx    = CE_INVALID_INDEX;
    bool        is_old = false;
    void*       blk    = nullptr;

    explicit operator bool() const
    {
        return blk;
    }

    bool operator<(Atom const& other) const
    {
        return this->idx < other.idx;
    }
};

struct Composite final
{
    std::vector<std::size_t> idxes;
    void*                    blk = nullptr;

    explicit operator bool() const
    {
        return blk && !idxes.empty();
    }

    void clear()
    {
        this->idxes.clear();
        this->blk = nullptr;
    }

    bool operator==(Composite const& other) const
    {
        return this->idxes.size() == other.idxes.size() &&
               std::equal(
                   this->idxes.begin(), this->idxes.end(), other.idxes.begin());
    }

    bool operator!=(Composite const& other) const
    {
        return !(*this == other);
    }

    bool operator<(Composite const& other) const
    {
        if (this->idxes.size() < other.idxes.size())
        {
            return true;
        }

        if (this->idxes.size() > other.idxes.size())
        {
            return false;
        }

        return std::lexicographical_compare(this->idxes.begin(),
                                            this->idxes.end(),
                                            other.idxes.begin(),
                                            other.idxes.end());
    }
};

inline std::size_t getAtomIndex(std::vector<Composite> const& composistes,
                                std::string const&            idxes)
{
    assert(composistes.size() > 1);
    assert(idxes.size() <= composistes.size());

    auto coll = std::map<std::size_t, std::size_t>{};
    for (auto const idx : idxes)
    {
        auto const& composite = composistes[static_cast<std::size_t>(idx)];
        for (auto const inner_idx : composite.idxes)
        {
            ++coll[inner_idx];
        }
    }

    for (auto const& item : coll)
    {
        if (1 == item.second % 2)
        {
            return item.first;
        }
    }

    return CE_INVALID_INDEX;
}

inline std::size_t getAtomIndex(std::vector<Composite> const& composistes,
                                std::size_t const             composite_idx)
{
    assert(composistes.size() > 1);
    assert(composite_idx < composistes.size() - 1);

    auto idxes = std::string{};
    idxes.push_back(static_cast<char>(composite_idx));
    idxes.push_back(static_cast<char>(composistes.size() - 1));
    return getAtomIndex(composistes, idxes);
}

inline void
eliminate(Composite& c, Atom const& a, std::size_t const payload_size)
{
    assert(a);
    assert(c);

    auto pos = std::find(c.idxes.begin(), c.idxes.end(), a.idx);
    if (pos == c.idxes.end())
    {
        return;
    }

    xor64(getPayloadPtr(a.blk),
          getPayloadPtr(c.blk),
          payload_size,
          getPayloadPtr(c.blk));
    c.idxes.erase(pos);
}

inline std::vector<char> fecDecode(std::vector<void*> const& bvs,
                                   std::size_t const         msg_size,
                                   std::size_t const         payload_size,
                                   std::size_t const         block_cnt)
{
    if (payload_size == msg_size)
    {
        auto ret = std::vector<char>{};
        ret.resize(msg_size);
        std::memcpy(ret.data(), getPayloadPtr(bvs[0]), msg_size);

        return ret;
    }

    assert(msg_size > payload_size && block_cnt > 1);
    assert(bvs.size() <= block_cnt * 2 + 1);

    if (bvs.size() < block_cnt)
    {
        return {};
    }

    auto const full_hdr_size        = getFullHeaderSize(bvs.front());
    auto const first_fec_blk_offset = payload_size * block_cnt;
    auto const super_fec_blk_offset = payload_size * block_cnt * 2;

    auto atoms         = std::vector<Atom>(block_cnt);
    auto composites    = std::vector<Composite>(block_cnt + 1);
    auto atom_cnt      = std::size_t{};
    auto composite_cnt = std::size_t{};

    for (auto const bv : bvs)
    {
        auto const payload_offset =
            static_cast<std::size_t>(getHeaderPtr(bv)->payload_offset);
        if (payload_offset < msg_size)
        {
            auto const idx  = payload_offset / payload_size;
            auto&      atom = atoms[idx];
            atom.idx        = idx;
            atom.blk        = bv;
            atom.is_old     = false;
            ++atom_cnt;
        }
        else if (payload_offset >= super_fec_blk_offset)
        {
            auto& composite = composites.back();
            composite.blk   = bv;
            composite.idxes.reserve(block_cnt + 1);
            ++composite_cnt;

            for (auto i = std::size_t{}; i < block_cnt; ++i)
            {
                composite.idxes.push_back(i);
            }
        }
        else
        {
            auto const idx =
                (payload_offset - first_fec_blk_offset) / payload_size;
            auto& composite = composites[idx];
            composite.blk   = bv;
            composite.idxes.reserve(block_cnt);
            ++composite_cnt;

            auto const idx_cnt = block_cnt - 1;
            for (auto i = std::size_t{}; i < block_cnt; ++i)
            {
                if (idx != idx_cnt - i)
                {
                    composite.idxes.push_back(i);
                }
            }
        }
    }

    auto const fn_gen_msg = [&]()
    {
        if (block_cnt != atom_cnt)
        {
            xout(123); // ???
        }

        assert(block_cnt == atom_cnt);

        auto ret = std::vector<char>(msg_size);
        auto len = std::size_t{};

        for (auto const& atom : atoms)
        {
            assert(atom);

            auto p = getPayloadPtr(atom.blk); // ???
            if (0 == std::memcmp(p, "\0\0\0\0", 4))
            {
                xout(atom.idx, _I_, atom.blk, _I_, static_cast<void*>(p));
                xout(bvs[0]);
                xout(bvs[1]);
                xout(std::hex,
                     std::size_t(p[0]),
                     _I_,
                     std::size_t(p[1]),
                     _I_,
                     std::size_t(p[2]),
                     _I_,
                     std::size_t(p[3]));
                atom_cnt--; // ???
            }

            auto remaining_len = ret.size() - len;
            auto n =
                remaining_len > payload_size ? payload_size : remaining_len;
            std::memcpy(ret.data() + len, getPayloadPtr(atom.blk), n);
            len += n;
            if (len >= ret.size())
            {
                break;
            }
        }

        return ret;
    };

    if (block_cnt == atom_cnt)
    {
        return fn_gen_msg();
    }

    auto new_atoms = std::map<std::size_t, Atom>{};

    auto const fn_eliminate = [&]()
    {
        new_atoms.clear();

        for (auto& atom : atoms)
        {
            if (nullptr == atom.blk)
            {
                continue;
            }

            if (atom.is_old)
            {
                continue;
            }

            for (auto pos = composites.begin(); pos != composites.end(); ++pos)
            {
                if (nullptr == pos->blk)
                {
                    continue;
                }

                eliminate(*pos, atom, payload_size);

                if (pos->idxes.empty())
                {
                    pos->clear();
                    --composite_cnt;
                    continue;
                }

                if (1 == pos->idxes.size())
                {
                    auto const atom_idx = pos->idxes.front();

                    if (atoms[atom_idx])
                    {
                        pos->clear();
                        --composite_cnt;
                        continue;
                    }

                    if (new_atoms.find(atom_idx) != new_atoms.end())
                    {
                        pos->clear();
                        --composite_cnt;
                        continue;
                    }

                    auto new_atom   = Atom{};
                    new_atom.blk    = pos->blk;
                    new_atom.idx    = atom_idx;
                    new_atom.is_old = false;

                    new_atoms[atom_idx] = std::move(new_atom);
                    pos->clear();
                    --composite_cnt;
                    continue;
                }
            }

            atom.is_old = true;
        }

        for (auto& composite : composites)
        {
            if (composite && composite.idxes.size() == 1)
            {
                auto const atom_idx = composite.idxes.front();
                auto       new_atom = Atom{};
                new_atom.blk        = composite.blk;
                new_atom.idx        = atom_idx;
                new_atom.is_old     = false;

                new_atoms[atom_idx] = std::move(new_atom);
                composite.clear();
                --composite_cnt;
                continue;
            }
        }
    };

    auto const fn_produce_ret = [&]() -> std::optional<std::vector<char>>
    {
        do
        {
            fn_eliminate();
            if (new_atoms.empty())
            {
                break;
            }

            for (auto& new_atom : new_atoms)
            {
                auto const idx = new_atom.first;
                if (nullptr == atoms[idx].blk)
                {
                    atoms[idx] = std::move(new_atom.second);
                    assert(atoms[idx].blk);
                    ++atom_cnt;
                }
            }

            if (block_cnt == atom_cnt)
            {
                return fn_gen_msg();
            }

            if (0 == composite_cnt)
            {
                return std::vector<char>{};
            }
        } while (true);

        if (block_cnt == atom_cnt)
        {
            return fn_gen_msg();
        }

        if (0 == composite_cnt)
        {
            return std::vector<char>{};
        }

        return std::nullopt;
    };

    if (auto opt_ret = fn_produce_ret())
    {
        return std::move(*opt_ret);
    }

    assert(!composites.empty());

    composites.erase(std::remove_if(composites.begin(),
                                    composites.end(),
                                    [](auto const& composite)
                                    { return nullptr == composite.blk; }),
                     composites.end());

    assert(!composites.empty());

    auto const idx_cnt                = composites.front().idxes.size();
    auto       idx_cnts_are_identical = true;

    for (auto const& composite : composites)
    {
        if (composite.idxes.size() != idx_cnt)
        {
            idx_cnts_are_identical = false;
            break;
        }
    }

    if (idx_cnts_are_identical)
    {
        if (0 == idx_cnt % 2)
        {
            // xout(idx_cnt, _I_, composite_cnt, _I_, block_cnt); // ???
            // assert(0 == idx_cnt || block_cnt == composite_cnt); // ???
            return {};
        }

        if (composites.size() < 2)
        {
            assert(idx_cnt >= 3);
            return {};
        }

        if (1 == idx_cnt)
        {
            for (auto& composite : composites)
            {
                auto const atom_idx = composite.idxes.front();
                if (atoms[atom_idx])
                {
                    continue;
                }

                atoms[atom_idx].idx = atom_idx;
                atoms[atom_idx].blk = composite.blk;
                composite.clear();
                ++atom_cnt;
            }

            assert(block_cnt == atom_cnt);
            return fn_gen_msg();
        }

        auto tmp_blks = std::deque<std::vector<char>>{};
        for (auto const& composite_idxes : genIndexVectors(composites.size()))
        {
            auto const atom_idx = getAtomIndex(composites, composite_idxes);

            assert(atom_idx < block_cnt);
            if (atoms[atom_idx])
            {
                continue;
            }

            tmp_blks.emplace_back(
                std::vector<char>(full_hdr_size + payload_size));

            auto atom = Atom{};
            atom.idx  = atom_idx;
            atom.blk  = tmp_blks.back().data();
            copyHeader(atom.blk, composites.front().blk, atom_idx);

            for (auto composite_idx : composite_idxes)
            {
                xor64(getPayloadPtr(atom.blk),
                      getPayloadPtr(
                          composites[static_cast<std::size_t>(composite_idx)]
                              .blk),
                      payload_size,
                      getPayloadPtr(atom.blk));
            }

            atoms[atom_idx] = std::move(atom);
            ++atom_cnt;
        }

        return fn_gen_msg();
    }

    std::sort(composites.begin(), composites.end());
    composites.erase(std::unique(composites.begin(), composites.end()),
                     composites.end());

    auto const& last_composite = composites.back();

    assert(composites.front().idxes.size() + 1 == last_composite.idxes.size());
    assert(composites.size() > 1);
    assert(composites[composites.size() - 2].idxes.size() + 1 ==
           last_composite.idxes.size());

    auto       tmp_blks = std::deque<std::vector<char>>{};
    auto const first_n  = composites.size() - 1;
    for (auto i = std::size_t{}; i < first_n; ++i)
    {
        if (composites[i].idxes.size() == 1)
        {
            auto const atom_idx = composites[i].idxes.front();
            assert(atom_idx < block_cnt);
            if (!atoms[atom_idx])
            {
                atoms[atom_idx].idx = atom_idx;
                atoms[atom_idx].blk = composites[i].blk;
                composites[i].clear();
                ++atom_cnt;
            }

            continue;
        }

        auto const atom_idx = getAtomIndex(composites, i);

        assert(atom_idx < block_cnt);
        if (atoms[atom_idx])
        {
            continue;
        }

        tmp_blks.emplace_back(std::vector<char>(full_hdr_size + payload_size));

        auto atom = Atom{};
        atom.idx  = atom_idx;
        atom.blk  = tmp_blks.back().data();
        copyHeader(atom.blk, composites.front().blk, atom_idx);

        auto const& composite = composites[i];
        xor64(getPayloadPtr(composite.blk),
              getPayloadPtr(last_composite.blk),
              payload_size,
              getPayloadPtr(atom.blk));

        atoms[atom_idx] = std::move(atom);
        ++atom_cnt;
    }

    if (block_cnt != atom_cnt)
    {
        assert(block_cnt == bvs.size());
        if (auto opt_ret = fn_produce_ret())
        {
            return std::move(*opt_ret);
        }

        return {};
    }

    assert(block_cnt == atom_cnt);
    return fn_gen_msg();
}
} // namespace rts

using namespace rts;

bool isWellFecEncoded(std::deque<std::vector<char>> const& blks,
                      std::size_t                          src_uid_len,
                      std::size_t                          dst_uid_len,
                      std::vector<char> const&             msg)
{
    auto const msg_size      = msg.size();
    auto const full_hdr_size = src_uid_len + dst_uid_len + sizeof(FixedHeader);
    auto const max_payload_size = CE_MTU - full_hdr_size;

    if (src_uid_len < 1 || dst_uid_len < 1 || src_uid_len > 32 ||
        dst_uid_len > 32 || msg_size > CE_MAX_MSG_SIZE)
    {
        return false;
    }

    if (blks.size() == 1)
    {
        return 0 ==
               std::memcmp(msg.data(), getPayloadPtr(blks[0].data()), msg_size);
    }

    auto const rounded_max_payload_size = static_cast<std::size_t>(
        roundDown<8>(static_cast<std::int64_t>(max_payload_size)));
    assert(rounded_max_payload_size <= max_payload_size);
    assert(0 == rounded_max_payload_size % 8);

    auto const block_cnt = msg_size % rounded_max_payload_size
                             ? msg_size / rounded_max_payload_size + 1
                             : msg_size / rounded_max_payload_size;

    auto const candidate_payload_size = static_cast<std::size_t>(
        roundUp<8>(static_cast<std::int64_t>(msg_size / block_cnt)));
    auto const payload_size = candidate_payload_size * block_cnt < msg_size
                                ? candidate_payload_size + 8
                                : candidate_payload_size;

    assert(payload_size * block_cnt >= msg_size);
    assert(payload_size * block_cnt < msg_size + payload_size);
    assert(0 == payload_size % 8);

    if (static_cast<std::size_t>(getHeaderPtr(blks.front().data())->msg_len) !=
        msg_size)
    {
        return false;
    }

    if (static_cast<std::size_t>(
            getHeaderPtr(blks.front().data())->payload_len) != payload_size)
    {
        xout(__LINE__,
             _I_,
             payload_size,
             _I_,
             getHeaderPtr(blks.front().data())->payload_len); // ???
        return false;
    }

    if (blks.size() != block_cnt * 2 + 1)
    {
        return false;
    }

    auto dst_msg = std::vector<char>(msg.size());
    auto len     = std::size_t{};

    for (auto i = std::size_t{}; i < block_cnt; ++i)
    {
        auto const n =
            msg_size - len >= payload_size ? payload_size : msg_size - len;
        std::memcpy(dst_msg.data() + len, getPayloadPtr(blks[i].data()), n);
        len += n;
        if (len >= msg_size)
        {
            break;
        }
    }

    assert(msg_size == len);

    if (std::memcmp(msg.data(), dst_msg.data(), msg_size))
    {
        auto n = 0;
        for (auto i = 0uz; i < msg.size(); ++i)
        {
            if (msg[i] != dst_msg[i])
            {
                xout("$"sv, i, _I_, int(msg[i]), _I_, int(dst_msg[i]));

                if (++n > 10)
                {
                    xout("ERROR: "sv,
                         __LINE__,
                         _I_,
                         msg.size(),
                         _I_,
                         dst_msg.size(),
                         _I_,
                         payload_size,
                         _I_,
                         block_cnt);
                    std::abort();
                }
            }
        }

        return false;
    }

    auto const ivs = genIndexVectors(block_cnt);
    auto       i   = block_cnt;
    for (auto const& iv : ivs)
    {
        auto payload = std::vector<char>(payload_size);
        for (auto idx : iv)
        {
            xor64(getPayloadPtr(blks[static_cast<std::size_t>(idx)].data()),
                  payload.data(),
                  payload_size,
                  payload.data());
        }

        if (std::memcmp(
                payload.data(), getPayloadPtr(blks[i].data()), payload_size))
        {
            return false;
        }

        ++i;
    }

    return true;
}

void testFec1()
{
    LOOP (idx, 10000)
    {
        auto msg = std::vector<char>(rand(1uz, 1027uz));
        randomize(msg);
        auto r = fecEncode("alice", 5, "bob", 3, false, msg.data(), msg.size());
        assert(isWellFecEncoded(r, 5, 3, msg));

        auto bvs = std::vector<void*>(r.size());
        for (auto i = 0uz; i < r.size(); ++i)
        {
            bvs[i] = r[i].data();
        }

        auto const msg_size =
            static_cast<std::size_t>(getHeaderPtr(bvs.front())->msg_len);
        auto const payload_size =
            static_cast<std::size_t>(getHeaderPtr(bvs.front())->payload_len);
        auto const block_cnt = msg_size % payload_size
                                 ? msg_size / payload_size + 1
                                 : msg_size / payload_size;

        auto recovered_msg = fecDecode(bvs, msg_size, payload_size, block_cnt);
        if (msg.size() != recovered_msg.size())
        {
            xout("ERROR: "sv, __LINE__);
            std::abort();
        }

        if (std::memcmp(msg.data(), recovered_msg.data(), msg.size()))
        {
            xout("ERROR: "sv, __LINE__);
            std::abort();
        }

        xout("testFec1: "sv, idx);
    }

    xout("GOOD: testFec1"sv);
}

struct LossCase final
{
    bool                     is_recoverable;
    std::vector<std::size_t> valid_idxes;
};

class Combinations final
{
    std::vector<std::size_t> cur_value_;
    std::size_t              n_;
    std::size_t              r_;

    std::size_t has_generated_;
    bool        is_completed_;

public:
    Combinations(std::size_t const n, std::size_t const r)
        : n_(n)
        , r_(r)
        , has_generated_{}
        , is_completed_(n < 1 || r > n)
    {
        for (std::size_t c = std::size_t(1); c <= r_; ++c)
        {
            cur_value_.push_back(c);
        }
    }

    bool isCompleted() const
    {
        return is_completed_;
    }

    std::vector<std::size_t> next(bool zero_based = false)
    {
        auto ret = cur_value_;

        is_completed_ = true;
        for (auto i = r_ - 1; i >= 0; --i)
        {
            if (cur_value_[i] < n_ - r_ + i + 1)
            {
                auto j = cur_value_[i] + 1;
                while (i <= r_ - 1)
                {
                    cur_value_[i++] = j++;
                }

                is_completed_ = false;
                ++has_generated_;
                break;
            }

            if (0 == i)
            {
                break;
            }
        }

        if (zero_based)
        {
            for (auto& i : ret)
            {
                --i;
            }
        }

        return ret;
    }
};

void testFec2()
{
    LOOP (index, 100)
    {
        auto msg_buf = std::vector<char>(rand(1213uz, 2027uz));
        randomize(msg_buf);
        auto const& msg = msg_buf;

        auto loss_cases = std::deque<LossCase>{};

        auto cs = Combinations(5, 5);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(5, 4);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(5, 3);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(5, 2);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
            if (std::vector<std::size_t>{0, 2} ==
                    loss_cases.back().valid_idxes ||
                std::vector<std::size_t>{1, 3} == loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
            }
        }

        cs = Combinations(5, 1);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = false;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        for (auto const& loss_case : loss_cases)
        {
            auto const  is_recoverable = loss_case.is_recoverable;
            auto const& idx_v          = loss_case.valid_idxes;

            auto r =
                fecEncode("alice", 5, "bob", 3, false, msg.data(), msg.size());
            assert(isWellFecEncoded(r, 5, 3, msg));
            auto bvs = std::vector<void*>{};
            for (auto idx : idx_v)
            {
                bvs.push_back(r[idx].data());
            }

            auto const msg_size =
                static_cast<std::size_t>(getHeaderPtr(bvs.front())->msg_len);
            auto const payload_size = static_cast<std::size_t>(
                getHeaderPtr(bvs.front())->payload_len);
            auto const block_cnt = msg_size % payload_size
                                     ? msg_size / payload_size + 1
                                     : msg_size / payload_size;

            auto recovered_msg =
                fecDecode(bvs, msg_size, payload_size, block_cnt);
            if (!is_recoverable)
            {
                if (!recovered_msg.empty())
                {
                    xout("ERROR: "sv,
                         __LINE__,
                         _I_,
                         msg.size(),
                         _I_,
                         recovered_msg.size(),
                         _I_,
                         payload_size,
                         _I_,
                         bvs.size(),
                         _I_,
                         block_cnt);
                    std::abort();
                }

                continue;
            }

            if (msg.size() != recovered_msg.size())
            {
                xout("ERROR: "sv,
                     __LINE__,
                     _I_,
                     msg.size(),
                     _I_,
                     recovered_msg.size(),
                     _I_,
                     payload_size,
                     _I_,
                     bvs.size(),
                     _I_,
                     block_cnt);
                std::abort();
            }

            if (std::memcmp(msg.data(), recovered_msg.data(), msg.size()))
            {
                std::copy(idx_v.begin(),
                          idx_v.end(),
                          std::ostream_iterator<std::size_t>(std::cout, ", "));
                std::cout << std::endl;

                auto n = 0;
                for (auto i = 0uz; i < msg.size(); ++i)
                {
                    if (msg[i] != recovered_msg[i])
                    {
                        xout("$"sv,
                             i,
                             _I_,
                             int(msg[i]),
                             _I_,
                             int(recovered_msg[i]));

                        if (++n > 10)
                        {
                            xout("ERROR: "sv,
                                 __LINE__,
                                 _I_,
                                 msg.size(),
                                 _I_,
                                 recovered_msg.size(),
                                 _I_,
                                 payload_size,
                                 _I_,
                                 bvs.size(),
                                 _I_,
                                 block_cnt);

                            isWellFecEncoded(r, 5, 3, msg);
                            std::abort();
                        }
                    }
                }

                xout("ERROR: "sv, __LINE__);
                std::abort();
            }
        }

        std::cout << "testFec2: "sv << index << std::endl;
    }

    xout("GOOD: testFec2"sv);
}

void testFec3()
{
    LOOP (index, 100)
    {
        auto msg_buf = std::vector<char>(rand(3100uz, 3500uz));
        randomize(msg_buf);
        auto const& msg = msg_buf;

        auto loss_cases = std::deque<LossCase>{};

        auto cs = Combinations(7, 7);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(7, 6);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(7, 5);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(7, 4);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(7, 3);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);

            if (std::vector<std::size_t>{0, 1, 3} ==
                loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
                continue;
            }

            if (std::vector<std::size_t>{0, 2, 4} ==
                loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
                continue;
            }

            if (std::vector<std::size_t>{1, 2, 5} ==
                loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
                continue;
            }

            if (std::vector<std::size_t>{0, 5, 6} ==
                loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
                continue;
            }

            if (std::vector<std::size_t>{1, 4, 6} ==
                loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
                continue;
            }

            if (std::vector<std::size_t>{2, 3, 6} ==
                loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
                continue;
            }

            if (std::vector<std::size_t>{3, 4, 5} ==
                loss_cases.back().valid_idxes)
            {
                loss_cases.back().is_recoverable = false;
                continue;
            }
        }

        cs = Combinations(7, 2);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = false;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(7, 1);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = false;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        for (auto const& loss_case : loss_cases)
        {
            auto const  is_recoverable = loss_case.is_recoverable;
            auto const& idx_v          = loss_case.valid_idxes;

            auto r =
                fecEncode("alice", 5, "bob", 3, false, msg.data(), msg.size());
            assert(isWellFecEncoded(r, 5, 3, msg));

            auto bvs = std::vector<void*>{};
            for (auto idx : idx_v)
            {
                std::cout << idx << ", "; // ???
                bvs.push_back(r[idx].data());
            }

            std::cout << std::endl; // ???

            if (std::vector<std::size_t>{3, 4, 6} == idx_v)
            {
                // xout("!!!");
            }

            auto const msg_size =
                static_cast<std::size_t>(getHeaderPtr(bvs.front())->msg_len);
            auto const payload_size = static_cast<std::size_t>(
                getHeaderPtr(bvs.front())->payload_len);
            auto const block_cnt = msg_size % payload_size
                                     ? msg_size / payload_size + 1
                                     : msg_size / payload_size;

            auto recovered_msg =
                fecDecode(bvs, msg_size, payload_size, block_cnt);
            if (!is_recoverable)
            {
                if (!recovered_msg.empty())
                {
                    xout("ERROR: "sv,
                         __LINE__,
                         _I_,
                         msg.size(),
                         _I_,
                         recovered_msg.size(),
                         _I_,
                         payload_size,
                         _I_,
                         bvs.size(),
                         _I_,
                         block_cnt);
                    std::abort();
                }

                continue;
            }

            if (msg.size() != recovered_msg.size())
            {
                print(idx_v);
                xout("ERROR size: "sv, __LINE__);
                std::abort();
            }

            if (std::memcmp(msg.data(), recovered_msg.data(), msg.size()))
            {
                print(idx_v);
                xout("ERROR contents: "sv, __LINE__);
                std::abort();
            }
        }

        std::cout << "testFec3: "sv << index << std::endl;
    }

    xout("GOOD: testFec3"sv);
}

void testFec4()
{
    LOOP (index, 100)
    {
        auto msg_buf = std::vector<char>(rand(4100uz, 4500uz));
        randomize(msg_buf);
        auto const& msg = msg_buf;

        auto loss_cases = std::deque<LossCase>{};

        auto cs = Combinations(9, 9);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(9, 8);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(9, 7);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(9, 6);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(9, 5);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(9, 3);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = true;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(9, 2);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = false;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        cs = Combinations(9, 1);
        while (!cs.isCompleted())
        {
            loss_cases.emplace_back();
            loss_cases.back().is_recoverable = false;
            loss_cases.back().valid_idxes    = cs.next(true);
        }

        for (auto const& loss_case : loss_cases)
        {
            auto const  is_recoverable = loss_case.is_recoverable;
            auto const& idx_v          = loss_case.valid_idxes;

            auto r =
                fecEncode("alice", 5, "bob", 3, false, msg.data(), msg.size());
            assert(isWellFecEncoded(r, 5, 3, msg));

            auto bvs = std::vector<void*>{};
            for (auto idx : idx_v)
            {
                std::cout << idx << ", "; // ???
                bvs.push_back(r[idx].data());
            }

            std::cout << std::endl; // ???

            if (std::vector<std::size_t>{3, 4, 6} == idx_v)
            {
                // xout("!!!");
            }

            auto const msg_size =
                static_cast<std::size_t>(getHeaderPtr(bvs.front())->msg_len);
            auto const payload_size = static_cast<std::size_t>(
                getHeaderPtr(bvs.front())->payload_len);
            auto const block_cnt = msg_size % payload_size
                                     ? msg_size / payload_size + 1
                                     : msg_size / payload_size;

            auto recovered_msg =
                fecDecode(bvs, msg_size, payload_size, block_cnt);
            if (is_recoverable)
            {
                if (msg.size() != recovered_msg.size())
                {
                    print(idx_v);
                    xout("ERROR size: "sv, __LINE__);
                    std::abort();
                }

                if (std::memcmp(msg.data(), recovered_msg.data(), msg.size()))
                {
                    print(idx_v);
                    xout("ERROR contents: "sv, __LINE__);
                    std::abort();
                }
            }
        }

        std::cout << "testFec4: "sv << index << std::endl;
    }

    xout("GOOD: testFec4"sv);
}

using namespace rts;

int main()
{
    testFec1();
    testFec2();
    testFec3();
    // testFec4();

    return 0;

    auto msg = std::string{};
    LOOP_N (1024 * 3 - 3)
    {
        msg += "A";
    }

    auto r =
        rts::fecEncode("alice", 5, "bob", 3, false, msg.data(), msg.size());
    xout("encoded block cnt: "sv, r.size());

    for (auto i = 0uz; i < r.size(); ++i)
    {
        auto const* p = rts::getHeaderPtr(r[i].data());
        xout(p->msg_id,
             _I_,
             p->msg_len,
             _I_,
             p->payload_offset,
             _I_,
             p->payload_len,
             _I_,
             int(p->src_uid_len),
             _I_,
             int(p->dst_uid_len),
             _I_,
             bool(p->fec_enabled));
        ++p;
    }

    auto bvs = std::vector<void*>{};
    bvs.reserve(r.size());

    auto n = 0;

    for (auto& item : r)
    {
        auto i = n++;
        if (0 == i || 4 == i || 5 == i)
        {
            continue;
        }

        bvs.emplace_back(item.data());
    }

    auto const msg_size =
        static_cast<std::size_t>(getHeaderPtr(bvs.front())->msg_len);
    auto const payload_size =
        static_cast<std::size_t>(getHeaderPtr(bvs.front())->payload_len);
    auto const block_cnt = msg_size % payload_size ? msg_size / payload_size + 1
                                                   : msg_size / payload_size;

    auto dr = fecDecode(bvs, msg_size, payload_size, block_cnt);

    FOR (idx, auto c : dr)
    {
        if (c != 'A')
        {
            xout("ERROR: ", dr.size(), _I_, idx, _I_, int(c));
            std::quick_exit(0);
        }
    }

    dr.back() = 0;
    xout(dr.data());
    xout(dr.size());
}